/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-07
 * Time: 23:00
 */
class ListNode {
    int val;
    ListNode next = null;
}
public class Soluton2 {
    /* 对于迭代：
            *               我们需要分成三部分，一个是前m个，m~n,后n个，所以我门肯定要找到m的前一个节点pre，找到n的后一个节点end
            *               然后翻转m~n,然后拼接上pre和end就可以了
            *               关键是如何翻转m~n，对于这个有一个比较高效的方法就是头插法变成倒序，也就是遍历到m的时候，不断让新的节点
           *               拼接到m位置的前面，也就是拼接到pre的后面，这样就实现了反转部分  */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //定义一个新的表头，即使m==1，也方便返回反转后的头结点
        ListNode newH=new ListNode();
        newH.next=head;
        //定义前驱节点，保证始终是m的前一个节点
        ListNode pre=newH;
        ListNode cur=head;
        //找到m的前一个位置
        for(int i = 1;i<m;i++){
            pre= cur;
            cur= cur.next;
        }
        //此时pre的位置就是m的前一个位置，cur的位置就是反转的第一个节点
        //开始反转m~n
        for(int i = m; i < n; i++){
            //循环让待反转部分的每一个节点一次成为反转的最后一个节点，这样原来的待反转的第一个节点就是成了待反转的最后一个节点
            //先记录当前节点的下一个节点
            ListNode tmp=cur.next;
            //把当前节点的后继节点接到tmp的下一个节点
            cur.next=tmp.next;
            //反转两个节点
            tmp.next =pre.next;
            //头插法，从当前节点下一个节点开始依次拼接到pre的后面
            pre.next=tmp;
        }
        return newH.next;
    }
}
